package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

/**
 * description: 
 * @author zhufeng
 * @date 2024/2/26 0026 9:33
 * @version V1.0
 */
public class 二叉树中的第K大层和_2583 {
    public long kthLargestLevelSum(TreeNode root, int k) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        List<Long> levelsSum = new ArrayList<>();
        while (!queue.isEmpty()) {
            List<TreeNode> levels = new ArrayList<>(queue);
            long sum = 0L;
            queue.clear();
            for (TreeNode node : levels) {
                sum += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            levelsSum.add(sum);
        }
        if (levelsSum.size() < k) {
            return -1;
        }
        Collections.sort(levelsSum);
        return levelsSum.get(levelsSum.size() - k);
    }

    @Test
    public void testLevelSum () {
        TreeNode l4 = new TreeNode(4);
        TreeNode r4 = new TreeNode(6);
        TreeNode l3 = new TreeNode(3);
        TreeNode r3 = new TreeNode(7);
        TreeNode l2 = new TreeNode(2, l4, r4);
        TreeNode r2 = new TreeNode(1);
        TreeNode l1 = new TreeNode(8, l2, r2);
        TreeNode r1 = new TreeNode(9, l3, r3);
        TreeNode root = new TreeNode(5, l1, r1);
        int k = 2;
        System.out.println(kthLargestLevelSum(root, k));
    }
}
